|
Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key'〔(【引用サイトリンク】title=Graph500 benchmark specification (supercomputer performance evaluation) )〕) and explores the neighbor nodes first, before moving to the next level neighbors. BFS was invented in the late 1950s by E. F. Moore, who used it to find the shortest path out of a maze, and discovered independently by C. Y. Lee as a wire routing algorithm (published 1961). == Pseudocode == Input: A graph and a ''starting vertex'' of Output: All vertices reachable from labeled as explored. A non-recursive implementation of breadth-first search: Breadth-First-Search(Graph, root): for each node n in Graph: n.distance = INFINITY n.parent = NIL create empty queue Q root.distance = 0 Q.enqueue(root) while Q is not empty: current = Q.dequeue() for each node n that is adjacent to current: if n.distance == INFINITY: n.distance = current.distance + 1 n.parent = current Q.enqueue(n) 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Breadth-first search」の詳細全文を読む スポンサード リンク
|